//stack.cpp
/********************************************************************************
*																				*
*	Author:			Jared Szechy												*
*	Assignment:		Assignment 7												*
*	Class:			CPS-151														*
*	Instructor:		V. Starkley													*
*	Due Date:		October 26													*
*																				*
*	Implementation file for Stack ADT .											*
*																				*
********************************************************************************/


template <class ItemType>
struct NodeType;

#include <iostream>
using namespace std;


template <class ItemType>
struct NodeType
{
   ItemType info;
   NodeType<ItemType>* next;
};


template<class ItemType>
StackType<ItemType>::StackType()
{
    topPtr = NULL;
}

template <class ItemType>
StackType<ItemType>::~StackType()
{
    NodeType<ItemType>* tempPtr;

    while (topPtr != NULL)
    {
	    tempPtr = topPtr;
	    topPtr = topPtr->next;
	    delete tempPtr;
     }
}

template <class ItemType>
StackType<ItemType>::StackType(const StackType<ItemType>& source)
{
	NodeType<ItemType>* sourcePtr;
	NodeType<ItemType>* selfPtr;

	if (source.topPtr == NULL)
		topPtr = NULL;
	else
	{
		topPtr = new NodeType<ItemType>;
		if (topPtr == NULL)
		{
			cout << "Insufficient memory.\n";
			exit(1);
		}
		topPtr->info = source.topPtr->info;
		sourcePtr = source.topPtr->next;
		selfPtr = topPtr;
		while (sourcePtr != NULL)
		{
			selfPtr->next = new NodeType<ItemType>;
			if (selfPtr->next == NULL)
			{
				cout << "Insufficient memory.\n";
				exit(1);
			}
			selfPtr = selfPtr->next;
			selfPtr->info = sourcePtr->info;
			sourcePtr = sourcePtr->next;
		}
		selfPtr->next =  NULL;
	}
}



template <class ItemType>
StackType<ItemType> StackType<ItemType>::operator = (const StackType<ItemType>& source)
{
	//check x==x case:
	if (this == &source)
		return *this;
	
	//destroy current elements in self
	NodeType<ItemType>* tempPtr;
    while (topPtr != NULL)
    {
		tempPtr = topPtr;
	   	topPtr = topPtr->next;
	   	delete tempPtr;
    }

	//copy source into self
	NodeType<ItemType>* sourcePtr;
	NodeType<ItemType>* selfPtr;
	if (source.topPtr == NULL)
		topPtr = NULL;
	else
	{
		topPtr = new NodeType<ItemType>;
		if (topPtr == NULL)
		{
			cout << "Insufficient memory.\n";
			exit(1);
		}
		topPtr->info = source.topPtr->info;
		sourcePtr = source.topPtr->next;
		selfPtr = topPtr;
		while (sourcePtr != NULL)
		{
			selfPtr->next = new NodeType<ItemType>;
			if (selfPtr->next == NULL)
			{
				cout << "Insufficient memory.\n";
				exit(1);
			}
			selfPtr = selfPtr->next;
			selfPtr->info = sourcePtr->info;
			sourcePtr = sourcePtr->next;
		}
		selfPtr->next =  NULL;
	}
	return (*this);
}


template <class ItemType>
void StackType<ItemType>::MakeEmpty() 
{
    NodeType<ItemType>* tempPtr;
    while (topPtr != NULL)
    {
	    tempPtr = topPtr;
	    topPtr = topPtr->next;
	    delete tempPtr;
     }
}

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
    NodeType<ItemType>* ptr;
    ptr = new NodeType<ItemType>;
    if (ptr == NULL)
	    return true;
    else
    {
	    delete ptr;
	    return false;
    }
}


template <class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
    return (topPtr == NULL);
}


template <class ItemType>
bool StackType<ItemType>::Push(ItemType item)
{
    NodeType<ItemType>* newNodePtr;
    newNodePtr = new NodeType<ItemType>;
	if (newNodePtr == NULL)
		return false;
    newNodePtr->info = item;
    newNodePtr->next = topPtr;
    topPtr = newNodePtr;
	return true;
}

template<class ItemType>
bool StackType<ItemType>::Pop(ItemType& item)
{
	if (topPtr == NULL)
		return false;
    item = topPtr->info;
    NodeType<ItemType>* tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
	return true;
}

template<class ItemType>
bool StackType<ItemType>::Identical(StackType<ItemType>& s1)
{
	NodeType<ItemType>* tempTop1;
	tempTop1 = topPtr;
	NodeType<ItemType>* tempTop2;
	tempTop2 = s1.topPtr;

	while(tempTop1 != NULL && tempTop2 != NULL)
	{
		if (tempTop1->info != tempTop2->info)
			return false;
		tempTop1 = tempTop1->next;
		tempTop2 = tempTop2->next;
	}
	if ((tempTop1 != NULL && tempTop2 == NULL) || (tempTop1 == NULL && tempTop2 != NULL))
		return false;
	else
		return true;
}

template<class ItemType>
StackType<ItemType> StackType<ItemType>::appendStack(StackType& aStack)
{
	
	if (aStack.topPtr == NULL)
	{
		if(topPtr == NULL)
		{
			StackType<ItemType> tempStack;
			return tempStack;
		}
		else
		{
			StackType<ItemType> tempStack(*this);
			return tempStack;
		}
	}
	else
	{
		if (topPtr == NULL)
		{
			StackType<ItemType> tempStack(aStack);
			return tempStack;
		}
	}

	StackType<ItemType> tempStack(*this);
	NodeType<ItemType>* lastItem;
	NodeType<ItemType>* tempTop;
	tempTop = tempStack.topPtr;

	while (tempTop != NULL)
	{
		lastItem = tempTop;
		tempTop = tempTop->next;
	}
	lastItem->next = aStack.topPtr;	

	return tempStack;
}

template<class ItemType>
void StackType<ItemType>::splitStack(StackType<ItemType>& stack1, StackType<ItemType>& stack2, ItemType splitValue)
{
	stack1.topPtr = NULL;
	stack2.topPtr = NULL;

	NodeType<ItemType>* endPtr1 = NULL;
	NodeType<ItemType>* endPtr2 = NULL;


	while (topPtr != NULL)
	{
		if (topPtr->info < splitValue)
		{
			if (stack1.topPtr == NULL)
			{
				stack1.topPtr = topPtr;
				endPtr1 = stack1.topPtr;
			}
			else
			{
				endPtr1->next = topPtr;
				endPtr1 = endPtr1->next;
			}
		}
		if (topPtr->info >= splitValue)
		{
			if (stack2.topPtr == NULL)
			{
				stack2.topPtr = topPtr;
				endPtr2 = stack2.topPtr;
			}
			else
			{
				endPtr2->next = topPtr;
				endPtr2 = endPtr2->next;
			}
		}
	topPtr = topPtr->next;
	}
}